package com.xsherl.leetcode.solution;

import com.xsherl.leetcode.utils.PrintUtils;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Combinations {

    /**
     * dfs
     *
     * 通过交换来重新排列元素顺序，
     * 每次交换的位置是遍历的位置 i 和 遍历的次数 l ，
     * 为了避免重复组合，下次遍历的开始位置为 i + 1
     * 比如：  1 2 3 4
     * 第一次：1 2 3 4
     * 第二次：1 3 2 4
     * 第三次：1 4 3 2
     * 第四次：2 3 1 4
     * 第五次：2 4 3 1
     * 第六次：3 4 1 2
     *
     */
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        int[] arr = new int[n];
        for (int i = 1; i <= n; ++i){
            arr[i - 1] = i;
        }
        combine(n, k, 1, 0, arr, res);
        return res;
    }

    private void combine(int n, int k, int index, int len, int[] arr, List<List<Integer>> res){
        if (len == k){
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < len; ++i){
                list.add(arr[i]);
            }
            res.add(list);
            return;
        }
        for (int i = index; i <= n; ++i){
            swap(arr, i - 1, len);
            combine(n, k, i + 1, len + 1, arr, res);
            swap(arr, i - 1, len);
        }
    }

    private void swap(int[] arr, int i, int j){
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }


    public static void main(String[] args) {
        List<List<Integer>> combine = new Combinations().combine(4, 2);
        PrintUtils.println(combine);
    }
}
